#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
    vector<string> ret;
    string path;

    string hash[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    vector<string> letterCombinations(string digts) {
        if (digts.size() == 0)
        {
            return ret;
        }

        dfs(digts, 0);
        return ret;
    }

    void dfs(string& digts, int pos)
    {
        if (pos == digts.size())
        {
            ret.push_back(path);
            return;
        }

        for (auto ch : hash[digts[pos] - '0'])
        {
            path.push_back(ch);
            dfs(digts, pos + 1);
            path.pop_back();
        }
    }
};